package com.husd.leetcode.tree;

import com.husd.leetcode.entry.TreeNode;

/**
 * 这里是一个二叉搜索树的例子代码
 * <p>
 * 主要有insert 和 delete 2个核心方法
 * print方法用来看树的结构的。
 *
 * @author hushengdong
 */
public class BinaryTree implements Tree {

    private TreeNode head;

    @Override
    public void insert(int value) {

        //相对简单的插入算法。
        TreeNode z = new TreeNode(value);
        TreeNode y = null;
        TreeNode x = head;
        while (x != null) {
            //y是x的父节点，前一个节点。
            y = x;
            if (z.value < x.value) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        //把z的位置挂到最终的合适的位置上去。
        if (y == null) {
            //表示head就是null，没有找到合适的位置，那么就是空节点。
            head = z;
        } else if (z.value < (int) y.value) {
            y.left = z;
        } else {
            y.right = z;
        }
    }

    @Override
    public void delete(int value) {

        if (head == null) return;

        TreeNode y = null;
        TreeNode z = head;

        while (z.value != value && z != null) {
            y = z;
            if (z.value < value) {
                z = z.right;
            } else {
                z = z.left;
            }
        }

        //找到了，或者没找到
        if (z == null) {
            //没找到
            return;
        }
        if (y == null) {
            //找到了，并且是根节点
            if (z.left == null) {
                head = z.right;
            } else if (z.right == null) {
                head = z.left;
            } else {
                TreeNode l = head.left;
                head = z.right;
                TreeNode zl = findZl(z.right);
                zl.left = l;
            }
            return;
        }
        boolean left = value < y.value;
        //找到了 分3种情况
        if (z.left == null && z.right == null) {
            //1 z没有子节点，是叶子节点，直接删除就行了。
            if (left) {
                y.left = null;
            } else {
                y.right = null;
            }
        } else if (z.left != null && z.right != null) {
            //2 z有二个子节点 这个节点，还可能是根节点
            // 后继节点肯定位于z的右节点，而且这个右节点，没有左节点
            TreeNode zl = findZl(z.right);
            y.right = z.right;
            zl.left = z.left;
        } else if (z.left != null && z.right == null) {
            //3 z有一个子节点，提升即可
            if (left) {
                y.left = z.left;
            } else {
                y.right = z.left;
            }
        } else if (z.left == null && z.right != null) {
            //3 z有一个子节点，提升即可
            if (left) {
                y.left = z.right;
            } else {
                y.right = z.right;
            }
        }
    }

    @Override
    public TreeNode find(TreeNode root, int value) {

        while (root != null && root.value != value) {
            if (root.value < value) {
                root = root.right;
            } else if (root.value > value) {
                root = root.left;
            } else if (root.value == value) {
                return root;
            }
        }
        return null;
    }

    @Override
    public int depth(TreeNode node) {

        return node == null ? 0 : (1 + Math.max(depth(node.left), depth(node.right)));
    }

    //这个版本是算法导论的版本 推荐
    public void delete2(int value) {

        if (head == null) return;

        TreeNode y = null;
        TreeNode z = head;

        while (z.value != value && z != null) {
            y = z;
            if (z.value < value) {
                z = z.right;
            } else {
                z = z.left;
            }
        }

        //找到了，或者没找到
        if (z == null) {
            //没找到
            return;
        }
        if (y == null) {
            //找到了，并且是根节点
            if (z.left == null) {
                head = z.right;
            } else if (z.right == null) {
                head = z.left;
            } else {
                TreeNodeWithPre treeNodeWithPre = findZlWithPre(z, z.right);
                TreeNode t = treeNodeWithPre.t;
                TreeNode pre = treeNodeWithPre.pre;
                TreeNode tr = t.right;
                TreeNode zl = head.left;
                head = t;
                t.left = zl;
                if (pre == z) {
                    t.right = null;
                } else {
                    t.right = z.right;
                    pre.left = tr;
                }
            }
            return;
        }
        boolean left = value < y.value;
        //找到了 分3种情况
        if (z.left == null && z.right == null) {
            //1 z没有子节点，是叶子节点，直接删除就行了。
            if (left) {
                y.left = null;
            } else {
                y.right = null;
            }
        } else if (z.left != null && z.right != null) {
            //2 z有二个子节点 这个节点，还可能是根节点
            // 后继节点肯定位于z的右节点，而且这个右节点，没有左节点
            // t代替z的位置
            TreeNodeWithPre treeNodeWithPre = findZlWithPre(z, z.right);
            TreeNode t = treeNodeWithPre.t;
            TreeNode pre = treeNodeWithPre.pre;
            TreeNode tr = t.right;
            if (left) {
                y.left = t;
            } else {
                y.right = t;
            }
            t.left = z.left;
            if (pre == z) {
                t.right = null;
            } else {
                t.right = z.right;
                pre.left = tr;
            }
        } else if (z.left != null && z.right == null) {
            //3 z有一个子节点，提升即可
            if (left) {
                y.left = z.left;
            } else {
                y.right = z.left;
            }
        } else if (z.left == null && z.right != null) {
            //3 z有一个子节点，提升即可
            if (left) {
                y.left = z.right;
            } else {
                y.right = z.right;
            }
        }
    }

    private TreeNode findZl(TreeNode node) {

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    private TreeNodeWithPre findZlWithPre(TreeNode pre, TreeNode node) {

        while (node.left != null) {
            pre = node;
            node = node.left;
        }
        TreeNodeWithPre treeNodeWithPre = new TreeNodeWithPre();
        treeNodeWithPre.pre = pre;
        treeNodeWithPre.t = node;
        return treeNodeWithPre;
    }

    public TreeNode getHead() {
        return head;
    }

    public void setHead(TreeNode head) {
        this.head = head;
    }

}
